package 二分查找;

/**
 * @author xiaok
 * @create 2020--09-08 14:15
 */

public class 求开方_69 {
   /*
    Input : [1,2,3,4,5]
    key : 3
            return the index : 2
    Copy to clipboardErrorCopied
    m 计算

有两种计算中值 m 的方式：

m = (l + h) / 2
m = l + (h - l) / 2
l + h 可能出现加法溢出，也就是说加法的结果大于整型能够表示的范围。但是 l 和 h 都为正数，因此 h - l 不会出现加法溢出问题。
所以，最好使用第二种计算法方法。
折半查找
    */
    public int binarySearch(int[] nums, int key) {
        int l = 0, h = nums.length - 1;
        while (l <= h) {
            int m = l + (h - l) / 2;
            if (nums[m] == key) {
                return m;
            } else if (nums[m] > key) {
                h = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
}
